#include <algorithm>
#include <cassert>
#include <string>

using namespace std;

class Solution {
public:
    string reverseWords(string s /* the sky is blue */) {
        reverse(s.begin(), s.end()); /* eulb si yks eht */

        int n = s.size();
        int idx = 0;

        // 遍历反转后的字符串
        for (int start = 0; start < n; ++start) {
            // 找到非空格字符开始的单词
            if (s[start] != ' ') {
                // 如果不是第一个单词，则在单词之前添加一个空格
                if (idx != 0) {
                    s[idx++] = ' ';
                }

                // 记录单词的起始位置
                int end = start;

                // 找到单词的末尾位置
                while (end < n && s[end] != ' ') {
                    s[idx++] = s[end++];
                }

                // 反转单词
                reverse(s.begin() + idx - (end - start), s.begin() + idx);

                // 更新起始位置为单词的末尾
                start = end;
            }
        }

        // 删除多余的字符
        s.erase(s.begin() + idx, s.end());

        return s;
    }
};

void test() {
    Solution s;

    string input1 = "the sky is blue";
    string input2 = "a good   example";
    string output1 = "blue is sky the";
    string output2 = "example good a";

    assert(s.reverseWords(input1) == output1);
    assert(s.reverseWords(input2) == output2);
}

int main() {
    test();
    return 0;
}